9032. Обновление дорог

 

В Берляндии есть n городов, соединённых m двусторонними дорогами. Дороги не могут соединять город с самим собой, и каждая пара городов соединяется не более чем одной дорогой. Не гарантируется, что из любого города можно добраться до любого другого, используя только существующие дороги.

Мэр города, Гаджи Ибрахим, решил внести изменения в систему дорожных путей и поручил министерству транспорта провести реформу. Теперь каждая дорога должна стать односторонней, то есть вести только в одном направлении – из одного города в другой.

Чтобы избежать недовольства жителей, необходимо провести реформу так, чтобы обособленных городов стало как можно меньше. Город считается обособленным, если в него не входит ни одна дорога (при этом допустимы дороги, выходящие из этого города).

Помогите Гаджи Ибрагиму найти минимальное количество обособленных городов после проведения реформы.

 

Вход. Первая строка содержит два натуральных числа n и m (2 ≤ n ≤ 105, 1 ≤ m ≤ 105) – количество городов и дорог в Берляндии.

В следующих m строках содержатся описания дорог: i-я дорога задаётся двумя различными целыми числами xi и yi (1 ≤ xi, yi ≤ n, xi ≠ yi), где xi и yi – номера городов, которые соединяет i-я дорога.

Гарантируется, что между каждой парой городов не может быть более одной дороги, но не гарантируется, что из любого города можно доехать до любого другого, используя только имеющиеся дороги.

 

Выход. Выведите одно число – минимальное количество обособленных городов после проведения реформы.

 

Пример входа 1

Пример выхода 1

4 3

2 1

1 3

4 3

1

 

 

Пример входа 2

Пример выхода 2

5 5

2 1

1 3

2 3

2 5

4 3

0

 

 

РЕШЕНИЕ

дерево

 

Анализ алгоритма

Рассмотрим неориентированный граф и выделим в нём компоненты связности. Если компонента связности представляет собой дерево (то есть не содержит циклов), всегда можно направить рёбра так, чтобы осталась ровно одна вершина без исходящих рёбер. Это означает, что в компоненте, являющейся деревом, количество обособленных городов после реформы можно сделать минимальным и равным 1 (нулевое количество невозможно). Например, обособленным городом можно сделать корень дерева.

 

Если в компоненте связности присутствует цикл, то ребра всегда можно ориентировать так, чтобы не существовало вершин без исходящих ребер.

Ответом на задачу будет количество компонент связности без циклов.

 

Пример

Рассмотрим первый пример. Слева показан исходный граф, а справа – граф после реформы. Вершина 1 не имеет исходящих ребер.

 

Рассмотрим второй пример. Слева показан исходный граф, а справа – граф после реформы. В каждой вершине имеется исходящее ребро.

 

Реализация алгоритма

Объявим список смежности g для хранения графа. Также объявим массив used для отмечания пройденных вершин.

 

vector<vector<int> > g;

vector<int> used;

 

Функция dfs выполняет поиск в глубину из вершины v. Предком вершины v является вершина p.

 

void dfs(int v, int p = -1)

{

  used[v] = 1;

  for (int to : g[v])

  {

    if (to == p) continue;

 

Если в текущей компоненте связности обнаружен цикл, установим flag = 0.

 

    if (used[to] == 1) flag = 0;

    else dfs(to, v);

  }

}

 

Основная часть программы. Читаем входные данные.

 

scanf("%d %d", &n, &m);

g.resize(n + 1);

used.resize(n + 1);

 

Читаем m ребер. Строим граф.

 

for (i = 0; i < m; i++)

{

  scanf("%d %d", &a, &b);

  g[a].push_back(b);

  g[b].push_back(a);

}

 

Запускаем поиск в глубину на несвязном графе. В переменной res подсчитываем количество компонент связности, не содержащих циклов.

 

res = 0;

for (i = 1; i <= n; i++)

{

  if (used[i] == 0)

 

  {

 

Изначально установим flag = 1. Если текущая компонента связности содержит цикл, то после вызова dfs значение flag станет равным 0.

 

    flag = 1;

    dfs(i);

    res += flag;

  }

}

 

Выводим ответ.

 

printf("%d\n", res);